package 经典排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

public class NC119最小的K个数 {

    /**
     * 给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组
     * 示例1
     * 输入
     * 复制
     * [4,5,1,6,2,7,3,8],4
     * 返回值
     * 复制
     * [1,2,3,4]
     */

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list=new ArrayList<>();
        if(k>input.length){
            return list;
        }
        if(k==input.length){
            Arrays.sort(input);
            for (int i : input) {
                list.add(i);
            }
            return list;
        }
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>((o1,o2)->o2-o1);

        for (int i : input) {
            priorityQueue.add(i);
            if(priorityQueue.size()>k){
                priorityQueue.remove();
            }
        }

        while (!priorityQueue.isEmpty()){
            list.add(priorityQueue.poll());
        }

        Collections.reverse(list);

        return list;
    }

}
